package leetcode;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 227.基本计算机Ⅱ
 * 给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。 整数除法仅保留整数部分。
 * 输入：s = "3+2*2"
 * 输出：7
 * 输入：s = " 3+5 / 2 "
 * 输出：5
 */
public class Num_227 {

    //双栈
    public static int calculate(String s) {

        //s1存放数字
        Stack<Integer> s1 = new Stack<>();
        //s2存放运算符
        Stack<Character> s2 = new Stack<>();
        //存放运算符的优先级
        Map<Character,Integer> map = new HashMap<>();
        map.put('+',1);
        map.put('-',1);
        map.put('*',2);
        map.put('/',2);

        for(int i=0; i<s.length();) {
            char c = s.charAt(i);
            //判断第i个字符是否为数字
            if(Character.isDigit(c)) {
                //如果第i个字符是数字,则需要找到数字结束点
                int j = i;
                while(j+1<s.length() && Character.isDigit(s.charAt(j+1))) {
                    j++;
                }
                //此时从i到j个字符都是数字
                String digit = s.substring(i,j+1);
                //将数字添到s1栈中
                s1.push(Integer.parseInt(digit));
                //字符位置后移
                i = j + 1;
            }else {
                /**
                 * 该字符是运算符
                 * 如果是* /，无论下一个运算符是什么，都可以先计算这一步运算的结果
                 * 如果是+ -，只有下一个运算符也是+ -的情况，才能先计算这一步的运算
                 */
                while(!s2.isEmpty() && map.get(s2.peek()) >= map.get(c)) {
                    //s2不为空 且 上一个运算符的优先级 >= 当前运算符的优先级
                    //此时可以先计算上一步的运算
                    int right = s1.pop();
                    int left = s1.pop();
                    char c2 = s2.pop();
                    int ret = 0;
                    if(c2 == '+'){
                        ret = left + right;
                    }else if(c2 == '-'){
                        ret = left - right;
                    }else if(c2 == '*'){
                        ret = left * right;
                    }else{
                        ret = left / right;
                    }
                    s1.push(ret);
                }
                //把当前运算符放到s2中
                s2.push(c);
                //字符位置后移
                i++;
            }
        }
        //此时，s2中优先级高的运算符一定在栈顶，可以依次弹出数字和运算符进行计算
        int result = 0;
        while(!s2.isEmpty()) {
            int right = s1.pop();
            int left = s1.pop();
            char c2 = s2.pop();
            if(c2 == '+'){
                result = left + right;
            }else if(c2 == '-'){
                result = left - right;
            }else if(c2 == '*'){
                result = left * right;
            }else{
                result = left / right;
            }
            s1.push(result);
        }
        return s1.peek();
    }

    public static void main(String[] args) {
        String str = "3+2*2";
        System.out.println(calculate(str));
    }
}
